/*
day321 
2020.7.14 
*/
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
    	if(nums.size()<2)
		{
			return nums;
		 } 
    	
		int num1=nums[0],num2=nums[1];
		int count1=0,count2=0;
		vector<int> res;
		
		for(int i=0;i<nums.size();++i)
		{
			if(nums[i]==num1)
			{
				count1++;
			}
			else if(nums[i]==num2)
			{
				count2++;
			}
			else
			{
				if(count1==0)
				{
					num1=nums[i];
					count1++;
				}
				else if(count2==0)
				{
					num2=nums[i];
					count2++;
				}
				else
				{
					count1--;
					count2--;
				}
			}
			
//			cout<<nums[i]<<'\t'
//			<<num1<<":"<<count1<<'\t'
//			<<num2<<":"<<count2<<endl;
		}
		
		count1=0; count2=0;
		for(int i=0;i<nums.size();++i)
		{
			if(nums[i]==num1)
			{
				count1++;
			}
			else if(nums[i]==num2)
			{
				count2++;
			}
		}
		
		if(count1>nums.size()/3)
		{
			res.push_back(num1);
		}
		if(count2>nums.size()/3)
		{
			res.push_back(num2);
		}
		
		return res;
    }
};


int main()
{
	vector<int> vec={4,2,1,1};
	Solution s;
	s.majorityElement(vec);
	return 0;
 } 
